Input buffered ATM switches, and some types of switches using a combination of input and output buffering, require a device to resolve output buffer contention. Output buffer contention results when there are more packets destined to an output buffer than the switch can transport in a cell cycle time. In a packet switch, output buffer contention is a result of the non-deterministic nature of packet traffic since traffic to any switch output buffer can come from a number of input buffers. Therefore, some device is needed to arbitrate among the input buffer requests and decide which input buffers will be allowed to transmit a cell through the switch in the next cell cycle time.
There exists a number of contention resolution schemes. One such scheme is disclosed in the above-referenced patent application, which is assigned to the assignee of the present invention, wherein contention is resolved for any incoming ATM cell at the head of queue (HOQ) by comparing the physical output module address with same address for every other ATM cell situated at the HOQ. If two or more cells have the same output module address, contention is resolved according to the relative numerical top-down locations of the specific input buffers for these cells as modified by priority and fairness considerations.
The article titled "A Growable Packet (ATM) Switch Architecture: Design Principles and Applications" authored by Kai Y. Eng, Mark J. Karol and Y. S. Yeh, presented at the International Conference on Communications and published in the Proceedings at pp. 1159-1165, discusses a method to construct large switches based on three principles: a Generalized Knockout Principle which exploits the statistical behavior of packet arrivals to reduce interconnect complexity; output queuing which yields good delay/throughput performance; and distributed intelligence in routing packets to eliminate path conflicts.
The article titled "A Cell-Based Cross-Connect Switch for ATM Broadband Networks." authored by H. Uematsu, H. Matsunaga and H. Obara, presented at the Singapore International Conference on Networks, 1989, discloses a time reservation algorithm for contention resolution in input queuing cross-connect switches for ATM networks. The algorithm represents an advanced version of scheduling control and is implemented utilizing a pipeline technique to provide higher throughput than conventional three-phase algorithms under random traffic.
Another reservation-based contention resolution scheme is described in the article titled "Reservation-Based Contention Resolution Mechanism for Batcher-Banyan Packet Switches", authored by B. Bingham and H. Bussey, published in Electronics Letters, 23.sup.rd June 1988, Vol. 24, No. 13. The article utilizes a ring-like interconnection of packet switch interfaces to make output port reservations, resulting in a high-performance switch that is compact and reliable.
In the article titled "Contention-Based Reservation Protocol in Fibre Optic Local Area Network With Passive Star Topology" authored by H. B. Jeon and C. K. Un, published in Electronics Letters, 7.sup.th June 1990, Vol. 26, No. 12, a contention-based reservation protocol utilizing a separate control channel for a fibre optic LAN is discussed. An access protocol is presented which uses an improved reservation scheme that is simple, yields a good delay/throughput characteristic and can be used in any multi-channel network.
The schemes described above, and the other existing schemes, however, are performed electronically. Another method resolves contention photonically, as described in "Photonic Architecture for Scheduling Cell-Transmission in Asynchronous Transfer Mode Switches", authored by K. Rastani, T. V. Lakshman and A. Bagchi, presented at the Optical Fiber Communications Conference, Feb. 2-7, 1992, San Jose, Calif. The authors propose a photonic device based on a graph-coloring scheduling algorithm. A general case, such as where, during a transmission slot, an input port is connected to all its requested output ports or none at all, is considered.
Unlike electronic-based contention resolution, photonic contention resolution is less complex, has fewer problems associated with electromagnetic interference and synchronization, and is faster.